package xyz.scootaloo.oj.leetcode

import cn.hutool.core.lang.Console
import org.junit.Test
import xyz.scootaloo.oj.ds.TreeNode

/**
 * @author flutterdash@qq.com
 * @since 2021/4/29 16:44
 */
class P108 {

    fun sortedArrayToBST(nums: IntArray): TreeNode? {
        return build(nums, 0, nums.size - 1)
    }

    fun build(nums: IntArray, left: Int, right: Int): TreeNode? {
        if (left > right)
            return null
        val mid = (left + right).shr(1)
        val node = TreeNode(nums[mid])

        node.left = build(nums, left, mid - 1)
        node.right = build(nums, mid + 1, right)

        return node
    }

    @Test
    fun test0() {
        val input = intArrayOf(-10, -3, 0, 5, 9)
        val root = sortedArrayToBST(input)
        Console.log()
    }

}
